package com.example.demo.tixiban;

/**
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2022/2/12 13:51
 */
public class bitmap_位图的实现 {

    static class BitMap{

        private Long [] bit;

        /**
         * 一个long类型可以表示64个数字
         * 存放max个数 (max+64)64个
         * @param max
         */
        public BitMap(int max) {
            this.bit = new Long[(max+64)/64];
            for(int i=0;i<bit.length;i++){
                bit[i]=0L;
            }
        }

        /**
         * 添加一个数 在正确的二进制位置上 置为 1
         *  num/64 表示在Long数组的第几位
         *  num%64 标识在Long数组的第几位 上的 具体位数， 要转变成  0001000 这种形式， 左移
         *
         * 自己 或 上新增的数的位置 比如  自己 ||  1000  表示这个位置被占用了
         *
         *
         * 优化:
         *    num % 64 == num & 63
         *    num / 64 == num>>6
         * @param num
         */
        public void add(int num){
           bit[num/64] = bit[num/64] | (1<<(num%64));

        }

        /**
         *移除一个数 在正确的二进制位置上 置为0
         *  找到这个数，然后除了这个位置为0，其他置为1  然后进行&操作
         *  比如 这个数是 0001000  那么 bit[num/64] & 1110111
         *
         *  (1)找到这个 数的位置  num%64  比如 65 得到 1
         *  (2)1左移到位置次数 到具体位置  000010
         *  (3)取反  111101
         *  (4)&操作
         * 优化:
         *    num % 64 == num & 63
         *    num / 64 == num>>6
         * @param num
         */
        public void remove(int num){
            long fan = 63-num%64;

            bit[num/64] = bit[num/64] & ~(1<<num%64);

            // bit[num/64] = bit[num/64] & ~(1<<(num%64));
        }

        /**
         * 判断是否包含一个数
         *  (1) 找到这个数的位置,然后右移到第0位 bit[num/64]>>(num%64)
         *  (2) 现在这个数在第0位置，那么如果是奇数，说明存在
         *
         *  优化:
         *      x % 2 == x & 1
         *
         * @param num
         * @return
         */
        public boolean contains(int num){
            long left = bit[num/64]>>(num%64);
            if((left & 1) ==1){
                return true;
            }
            return false;

        }

    }

    public static void main(String[] args) {

        BitMap  map = new BitMap(100000);

        map.add(65);
        System.out.println(map.contains(65));
        map.remove(65);
        System.out.println(map.contains(65));
    }

}
